/*
 * @lc app=leetcode.cn id=878 lang=typescript
 *
 * [878] 第 N 个神奇数字
 */

// @lc code=start
function nthMagicalNumber(n: number, a: number, b: number): number {
  const mod = 10 ** 9 + 7;
  // 最小公约数
  const gcd = (a: number, b: number): number => {
    return b === 0 ? a : gcd(b, a % b);
  };
  // 最小公倍数
  const lcm = (a: number, b: number): number => {
    return (a * b) / gcd(a, b);
  };
  // 可以被a和b整除的数的个数
  const magicNumber = (n: number): number => {
    return Math.floor(n / a) + Math.floor(n / b) - Math.floor(n / lcm(a, b));
  };

  let l = 1;
  let r = n * Math.min(a, b);

  let mid: number;
  while (l < r) {
    mid = l + Math.floor((r - l) / 2);
    if (magicNumber(mid) < n) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }

  return l % mod;
}
// @lc code=end
